import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

    Map<Integer,Integer> map = new HashMap<>();
    public int Fibonacci (int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;

        int pre = 0;
        int ppre = 0;

        if (map.containsKey(n-2)){
            ppre = map.get(n-2);
        }else{
            ppre = Fibonacci(n-2);
            map.put(n-2,ppre);
        }

        if (map.containsKey(n-1)){
            pre = map.get(n-1);
        }else{
            pre = Fibonacci(n-1);
            map.put(n-1,pre);
        }


        return ppre + pre;
    }
}
